Path sum II

Time: O(N); Space: O(H); medium

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note:

  • A leaf is a node with no children.

Example 1:

Input: root = {TreeNode} [5,4,8,11,None,13,4,7,2,None,None,5,1], sum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Output:

[
   [5,4,11,2],
   [5,8,4,5]
]

Explanation:

  • The sum of the two paths is 22：

    • 5 + 4 + 11 + 2 = 22

    • 5 + 8 + 4 + 5 = 22

Example 2:

Input: root = {TreeNode} [10,6,7,5,2,1,8,None,9], sum = 18

     10
   /    \
  6      7
 / \    / \
5   2  1   8
 \
  9

Output:

[
    [10,6,2],
    [10,7,1]
]

Explanation:

  • The sum of the two paths is 18：

    • 10 + 6 + 2 = 18

    • 10 + 7 + 1 = 18

[4]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[5]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H), H is height of binary tree
    """
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        return self.pathSumRecu([], [], root, sum)

    def pathSumRecu(self, result, cur, root, sum):
        if root is None:
            return result

        if root.left is None and root.right is None and root.val == sum:
            result.append(cur + [root.val])
            return result

        cur.append(root.val)

        self.pathSumRecu(result, cur, root.left, sum - root.val)
        self.pathSumRecu(result, cur,root.right, sum - root.val)
        cur.pop()

        return result

[6]:

s = Solution1()

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.right.left = TreeNode(13)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(4)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(1)
sum = 22
assert s.pathSum(root, sum) == [
  [5,4,11,2],
  [5,8,4,5]
]

root = TreeNode(10)
root.left = TreeNode(6)
root.right = TreeNode(7)
root.left.left = TreeNode(5)
root.left.right = TreeNode(2)
root.right.left = TreeNode(1)
root.right.right = TreeNode(8)
root.left.left.right = TreeNode(9)
sum = 18
assert s.pathSum(root, sum) == [
  [10,6,2],
  [10,7,1]
]